package qujian;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
 * 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
 * 解释：
 * 编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
 * 编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
 * 编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
 * 编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 * 编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
 * 编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
 * 因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-04 10:52
 */
public class L406 {
    // * 输入：people = [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
    public int[][] reconstructQueue(int[][] people) {
        if (people.length == 1) return people;
        //排序，i 降序，j 升序，相同
        Arrays.sort(people, (x, y) -> x[0] == y[0] ? x[1] - y[1] : y[0] - x[0]);
        //根据j 插入链表
        List<int[]> list = new LinkedList<>();
        //后面添加的i更小，覆盖前面的同一个位置
        for (int i = 0; i < people.length; i++) {
            list.add(people[i][1], people[i]);
        }
        return list.toArray(new int[list.size()][]);
    }
}
